package com.itzmn.datastructure.newcode;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/31 13:38
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 小和
 *
 *  在一个数组中，每一个数左边比该数小的加起来，就是这个数的小和，求这个数组的小和
 *
 * 1.可以遍历每个数，计算每个数的小和然后累加
 *
 * 2.使用归并排序，在进行归并的时候，进行判断，如果右边该数比左边数大，说明右边数后面的数都比这个数大，
 *    然后计算，每一个都这样算
 */
public class SmallSum {

    public static void main(String[] args) {

        new SmallSum().init();
    }
    private void init() {
        int[] ints = {3, 4, 2, 5, 7, 6};
        int getsum = getsum(ints);
        System.out.println(getsum);
        for (int i=0;i<ints.length;i++){
            System.out.print(ints[i]+" ");
        }
    }

    private int getsum(int[] arr){

        int sort = sort(arr, 0, arr.length - 1);

        return sort;
    }


    /**
     *  将数组划分多个部分。
     * @param arr 数组
     * @param L 数组左边界
     * @param R 数组右边界
     */
    public int sort(int[] arr,int L,int R){

        if (L == R){
            return 0;
        }
        int res = 0;
        int mid = (L + R) /2 ;

        res += sort(arr,L,mid) + sort(arr,mid+1,R);

        // 合并两个数组
        res += merge(arr, L, R, mid);

        return res;
    }

    /**
     * 将分开的数组合并
     */
    public int merge(int[] arr,int L,int R,int mid){

        int[] help = new int[R - L + 1];

        int i = L,j=mid+1,k=0;

        int res = 0;
        while (i<=mid && j<=R){

            // 如果右边比左边小，说明可以计算小和
            if (arr[i] < arr[j]){
                res += (R-j+1)*arr[i];
            }

            help[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];

        }

        while (i <= mid){
            help[k++] = arr[i++];
        }
        while (j <= R){
            help[k++] = arr[j++];
        }


        for (int m=0;m<help.length;m++){
            arr[L++] = help[m];
        }
        return res;

    }
}
